package org.suanfaTranning.ST200_Chatpter1_LineTable_HashTable_String.hashTable;

/**
 * @Auther: qingle
 * @Date: 2024/9/11-1:12
 * @Description:
 * 我们可以采用一个巧妙的方法，结合双端队列（Deque）和哈希集合（HashSet）。这种方法的时间复杂度为 O(1)，空间复杂度也为 O(1)，非常适合处理高频率的请求。
 *
 * 实现思路
 * 双端队列：用于存储每个请求的时间戳。队列的前端（头部）用于 pop 操作，后端（尾部）用于 push 操作。
 *
 * 哈希集合：用于快速判断某个时间戳是否已经存在，从而避免重复存储。
 *
 * 操作流程：
 *
 * push(val)：将请求的时间戳推入双端队列的尾部，并将其加入哈希集合。
 * pop()：从双端队列的头部移除元素，直到找到第一个非空的时间戳，然后返回这个时间戳对应的值，并从哈希集合中移除该时间戳。
 * getCount(t)：计算从 t - 3000 到 t 之间的请求次数。遍历双端队列，移除所有超出时间窗口的时间戳，并计数。
 * @version: 1.0
 */
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class RecentCounter2 {
	private final Deque<Integer> deque;

	public RecentCounter2() {
		deque = new LinkedList<>();
	}

	public int ping(int t) {
		deque.offerLast(t);
		// 移除所有过期的时间戳
		while (!deque.isEmpty() && deque.peekFirst() < t - 3000) {
			deque.pollFirst();
		}
		// 返回当前时间范围内的请求数量
		return deque.size();
	}

	public static void main(String[] args) {
		RecentCounter2 counter = new RecentCounter2();
		int[] timestamps = {1, 100, 3001, 3002};
		int[] expectedOutput = {1, 2, 3, 3};

		for (int timestamp : timestamps) {
			int result = counter.ping(timestamp);
			System.out.println(result); // 打印每次 ping 的结果
		}
	}
}